package 前缀系列;

/**
 * 手写 一下    前缀树 
 * @author I adore you
 *
 */

public class leetcode720词典中最长的单词 {
	
	public static void main(String []args) {
		TireTree t=new TireTree();
		t.add("abcdef");
		t.add("abchanjunhaoef");
		t.add("abczhangef");
		t.add("abchhff");
		t.add("bcdef");
		t.add("cdef");
		t.add("cdef");
//		t.delete("cdef");
		System.out.println(t.query("cdef"));
		System.out.println(t.preStringSum("abc"));
	}
	
	
	
	
	
	
	static class Node {
		int pass;
		int end;
		Node next[];
		public Node() {
			this.pass = 0;
			this.end = 0;
			next = new Node[26];// a ~ z 只能表示  小写字母 这26个 
		}
	}
	static class TireTree{
		private Node root;
		public TireTree() {
			this.root =  new Node();
		}
		
		
		
//		在字典树中 查找   以 str 字符串为前缀的 字符串的数目 
		public int  preStringSum(String str) {
			if(str == null) {
				return 0;
			}
			char []s = str.toCharArray();
			Node temp = root;
			int index = 0;
			for(int i = 0; i < s.length;i++) {
				index = s[i] - 'a';
//				if(temp.next[index] != null) {
//					temp = temp.next[index];
//				}
//     上面这样写 是错的   
				if(temp.next[index] == null) {
					return 0;
				}
				temp = temp.next[index];
				
				
			}
//			return temp.end;    注意是前缀和  返回 temp.pass 啊 这才是 正常的
			return temp.pass;
		}
		public boolean delete (String str) {
			if(str == null  || query(str)==0) {
				return false;
			}
			char []s = str.toCharArray();
			Node temp = root;
			temp.pass--;
//			temp.end--;
			int index = 0;
			for(int  i = 0;i< s.length;i++) {
				index = s[i]-'a';
				if(--temp.next[index].pass==0) {
					temp.next[index] = null;
//					  这里换成 break  会不会更好 一些
					return true;
				}
				temp = temp.next[index];
			}
			temp.end--;
			return true;
			
		}
		
		public void add(String str) {
			if(str == null) {
				return ;
			}
			Node temp =root;
			temp.pass++;
			char [] s= str.toCharArray();
			int len = s .length;
			int index =0;//  小优化  把 index 定义在外面
			for(int i = 0; i < len ;i++) {
				 index = s[i] - 'a';
//				if(temp.next[index] !=null) {
//					temp.next[index].pass++;
//					temp = temp.next[index];
//				}
//				else {
//					temp.next[index] = new Node();
//					temp.next[index].pass++;
//					temp = temp.next[index];
//					
//				}
				if(temp.next[index] == null) {
					temp.next[index] = new Node();
				}
//				temp.next[index].pass++; //   这是正确的 
				temp = temp.next[index];
//				temp.next[index].pass++;
				temp.pass++;
			}
			temp.end++;
		}
/**
 * 		 查询 某个 字符串 是否 在 字典序中存在 存在   
 * @param str
 * @return 
 * 考虑的 情况 有点太简单 了对吧 查询 str 出现可能 不只 一次  返回个 Boolean 值 不太合理
 */
		public int query(String str) {
			if(str ==null) {
				return 0;
			}
			Node  temp = root;
			char s[] =str.toCharArray();
			int index = 0;
			for(int i = 0; i < s.length;i++) {
				index = s[i] - 'a';
				if(temp.next[index]== null) {
					return 0;
				}
				temp = temp.next[index];
			}
			return temp.end;
		}
		
		
	}

}
